package editortrees;

// A node in a height-balanced binary tree with rank.
// Except for the NULL_sNODE (if you choose to use one), one node cannot
// belong to two different trees.

/**
 * A node of an EditTree
 * 
 * @author riechelp. Created Oct 17, 2012.
 */
public class Node {

	/**
	 * This code indicates which child has a greater height.
	 * 
	 * @author riechelp. Created Oct 17, 2012.
	 */
	enum Code {
		/**
		 * Both children of this node have equal heights
		 */
		SAME, /**
		 * The left child of this node has a greater height than the right.
		 */
		LEFT, /**
		 * The right child of this node has a greater height than the left.
		 */
		RIGHT
	};

	/**
	 * The element of this node
	 */
	// The fields would normally be private, but for the purposes of this class,
	// we want to be able to test the results of the algorithms in addition to
	// the
	// "publicly visible" effects

	char element;
	/**
	 * References to the left and right nodes/subtrees
	 */
	@SuppressWarnings("javadoc")
	Node left, right; // subtrees
	/**
	 * Size of the left subtree.
	 */
	int rank;
	/**
	 * The balance code of the node.
	 */
	Code balance;

	/**
	 * Constructs a new node with the given parameters
	 * 
	 * @param element
	 * @param left
	 * @param right
	 * @param rank
	 * @param balance
	 */
	public Node(char element, Node left, Node right, int rank, Code balance) {
		this.element = element;
		this.left = left;
		this.right = right;
		this.rank = rank;
		this.balance = balance;
	}

	/**
	 * Creates a node using the given string.
	 * 
	 * @param s
	 * @return the node
	 */
	public static Node CreateNode(String s) {

		// A balance code is to the left iff the size is a perfect log_2
		// otherwise it should be same
		// The balance calculation checks to see if the log_2 - the truncated
		// log_2 gives a value within the tolerance, meaning it is a perfect log
		Code balance = (Math.log10(s.length()) / Math.log10(2)
				- (double) ((int) (Math.log10(s.length()) / Math.log10(2) + 0.0001)) < 0.0001)
				&& (int) (Math.log(s.length()) / Math.log10(2)) != 0 ? Code.LEFT : Code.SAME;

		if (s.length() > 0) {
			char element = s.charAt(s.length() / 2);
			Node left = null;
			Node right = null;
			if (s.length() > 1) {
				left = CreateNode(s.substring(0, s.length() / 2));
				right = CreateNode(s.substring(s.length() / 2 + 1, s.length()));
			}

			return new Node(element, left, right, s.length() / 2, balance);
		} else {
			return null;
		}

	}

	/**
	 * Adds a node to the given tree at the given position, rebalancing as needed.
	 * 
	 * @param c
	 * @param pos
	 * @param tree
	 * @return the value return is whether or not the tree has been balanced yet so once you balance, it will return
	 *         straight out
	 */
	public AddItem add(char c, int pos, EditTree tree) {
		if (this.rank == pos) {
			if (this.left == null) {
				this.rank++;
				Node n = new Node(c, null, null, 0, Code.SAME);
				return addRebalanceLeft(new AddItem(false, n), tree);
			} else {
				this.rank++;
				AddItem n = this.left.addLower(c, tree);
				return addRebalanceLeft(n, tree);
			}

		} else if (this.rank > pos) { // we go into the left subtree
			this.rank++;
			return addRebalanceLeft(this.left.add(c, pos, tree), tree);

		} else { // we go into the right subtree
			return addRebalanceRight(this.right.add(c, pos - this.rank - 1, tree), tree);

		}
	}

	/**
	 * Goes as far right as it can and then inserts the node, rebalances on the way back up
	 * 
	 * @param c
	 * @param tree
	 * @return
	 */
	private AddItem addLower(char c, EditTree tree) {
		if (this.right == null) {
			Node n = new Node(c, null, null, 0, Code.SAME);
			return addRebalanceRight(new AddItem(false, n), tree);
		} else {
			return addRebalanceRight(this.right.addLower(c, tree), tree);

		}
	}

	/**
	 * balances the tree assuming it had and item added on it's left side
	 * 
	 * @param an
	 * @param tree
	 * @return
	 */
	private AddItem addRebalanceLeft(AddItem an, EditTree tree) {
		Node n = an.node;
		this.left = n;
		if (an.IsBalanced) {
			return new AddItem(true, this);
		}
		if (this.balance == Code.RIGHT) {
			this.balance = Code.SAME;
			return new AddItem(true, this);
		} else if (this.balance == Code.SAME) {
			this.balance = Code.LEFT;
			return new AddItem(false, this);
		} else {
			if (this.left.balance == Code.LEFT) // we need to do a single
												// shift right
				return new AddItem(true, tree.singleRotateRight(this, this.left));
			else { // we need to do a double shift right
				return new AddItem(true, tree.doubleRotateRight(this, this.left.right, this.left));
			}
		}
	}

	/**
	 * balances the tree assuming it had and item added on it's right side
	 * 
	 * @param an
	 * @param tree
	 * @return
	 */
	private AddItem addRebalanceRight(AddItem an, EditTree tree) {
		Node n = an.node;
		this.right = n;
		if (an.IsBalanced) {
			return new AddItem(true, this);
		}
		if (this.balance == Code.LEFT) {
			this.balance = Code.SAME;
			return new AddItem(true, this);
		} else if (this.balance == Code.SAME) {
			this.balance = Code.RIGHT;
			return new AddItem(false, this);
		} else {
			if (this.right.balance == Code.RIGHT) // we need to do a single
				// shift left
				return new AddItem(true, tree.singleRotateLeft(this, this.right));
			else { // we need to do a double shift left
				return new AddItem(true, tree.doubleRotateLeft(this, this.right.left, this.right));
			}

		}
	}

	/**
	 * Recursively deletes the item at the given position, potentially using the recursive method delete lower
	 * 
	 * @param pos
	 * @param editTree
	 * @return DeletedItem
	 */
	public DeleteItem delete(int pos, EditTree editTree) {
		if (this.rank == pos) {
			if (this.left == null) {
				return new DeleteItem(false, this.right, this.element);
			}
			if (this.right == null) {
				return new DeleteItem(false, this.left, this.element);
			}

			DeleteItem rightChild = this.right.deleteLower(editTree);
			this.element = rightChild.c;
			return deleteRebalanceRight(rightChild, editTree);

		} else if (this.rank > pos) { // we go into the left subtree
			this.rank--;
			DeleteItem leftChild = this.left.delete(pos, editTree);
			return deleteRebalanceLeft(leftChild, editTree);

		} else { // we go into the right subtree
			DeleteItem rightChild = this.right.delete(pos - this.rank - 1, editTree);
			return deleteRebalanceRight(rightChild, editTree);
		}
	}

	/**
	 * Goes as far left as it can and then deletes that node, returning back the node to the right
	 * 
	 * @param editTree
	 * @return
	 */
	private DeleteItem deleteLower(EditTree editTree) {
		if (this.left == null) {
			return new DeleteItem(false, this.right, this.element);
		}
		this.rank--;
		DeleteItem leftChild = this.left.deleteLower(editTree);
		return deleteRebalanceLeft(leftChild, editTree);
	}

	/**
	 * balances the tree assuming it had and item deleted on it's left side
	 * 
	 * @param leftChild
	 * @param editTree
	 * @return
	 */
	private DeleteItem deleteRebalanceLeft(DeleteItem leftChild, EditTree editTree) {
		this.left = leftChild.node;
		if (leftChild.IsBalanced == true) { // already been balanced so we
											// just need to go back up
			return new DeleteItem(true, this, leftChild.c);
		}
		if (this.balance == Code.SAME) { // this will balance it
											// because the height of
											// this subtree will be the
											// same as it was before
			this.balance = Code.RIGHT;
			return new DeleteItem(true, this, leftChild.c);
		}
		if (this.balance == Code.LEFT) {
			this.balance = Code.SAME;
			return new DeleteItem(false, this, leftChild.c);
		}
		Node n;
		if (this.right == null) {
			System.out.println("fail");
		}
		boolean isBalanced = false;
		if (this.right.balance == Code.RIGHT || this.right.balance == Code.SAME) {
			Node temp = this.right;
			n = editTree.singleRotateLeft(this, this.right);
			if(temp.balance != Code.SAME)
				isBalanced = true;
		} else {
			n = editTree.doubleRotateLeft(this, this.right.left, this.right);
		}
		return new DeleteItem(isBalanced, n, leftChild.c);
	}

	/**
	 * balances the tree assuming it had and item deleted on it's right side
	 * 
	 * @param rightChild
	 * @param editTree
	 * @return
	 */
	private DeleteItem deleteRebalanceRight(DeleteItem rightChild, EditTree editTree) {
		this.right = rightChild.node;
		if (rightChild.IsBalanced == true) { // already been balanced so we
												// just need to go back up
			return new DeleteItem(true, this, rightChild.c);
		}
		if (this.balance == Code.SAME) { // this will balance it
											// because the height of
											// this subtree will be the
											// same as it was before
			this.balance = Code.LEFT;
			return new DeleteItem(true, this, rightChild.c);
		}
		if (this.balance == Code.RIGHT) {
			this.balance = Code.SAME;
			return new DeleteItem(false, this, rightChild.c);
		}
		Node n;
		boolean isBalanced = false;
		if (this.left.balance == Code.LEFT || this.left.balance == Code.SAME) {
			Node temp = this.left;
			n = editTree.singleRotateRight(this, this.left);
			if(temp.balance != Code.SAME)
				isBalanced = true;
		} else {
			n = editTree.doubleRotateRight(this, this.left.right, this.left);
		}
		return new DeleteItem(isBalanced, n, rightChild.c);
	}

	// added for displaying purposes only
	/**
	 * the x location of a node for displaying
	 */
	public int xloc;
	/**
	 * the y location of a node for displaying
	 */
	public int yloc;

	/**
	 * Added for displaying purposes only
	 * 
	 * @param x
	 * @param y
	 * @return the count
	 */
	public int countInOrder(int x, int y) {
		this.yloc = y;
		if (this.left != null) {
			x = this.left.countInOrder(x, y + 1) + 1;
		}

		this.xloc = x;

		if (this.right != null) {
			x = this.right.countInOrder(x + 1, y + 1);
		}
		return x;
	}

	/**
	 * Returns the height of the node. This is a O(log(n)) operation.
	 * 
	 * @return height
	 */
	public int height() {

		int height = 0;
		if (this.balance == Code.LEFT) {
			height = this.left.height();
		} else { // if balance = same, it dosen't matter which side you go down
			if (this.right != null)
				height = this.right.height();
		}
		return 1 + height;
	}

	/**
	 * The size of the subtree with this node as the head.
	 * 
	 * @return the size of the subtree
	 */
	public int size() {
		int left = 0;
		int right = 0;
		if (this.left != null)
			left = this.left.size();
		if (this.right != null)
			right = this.right.size();
		return 1 + left + right;
	}

	/**
	 * Returns the element of the node
	 * 
	 * @return the element of the node
	 */
	public char getElement() {
		return this.element;
	}

	/**
	 * Returns the right child node.
	 * 
	 * @return the right child node
	 */
	public Node getRight() {
		return this.right;
	}

	/**
	 * Returns the left child node.
	 * 
	 * @return the left child node
	 */
	public Node getLeft() {
		return this.left;
	}

	/**
	 * Copies a tree starting in this node
	 *
	 * @return the copy
	 */
	public Node Copy() {

		if (this.left == null && this.right == null) {
			return new Node(this.element, null, null, this.rank, this.balance);
		}
		if (this.left == null)
			return new Node(this.element, null, this.right.Copy(), this.rank, this.balance);
		if (this.right == null)
			return new Node(this.element, this.left.Copy(), null, this.rank, this.balance);
		return new Node(this.element, this.left.Copy(), this.right.Copy(), this.rank, this.balance);
	}

}